﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//括号匹配问题
//https://leetcode.cn/problems/valid-parentheses/


typedef char STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;

}ST;
void Buynode(ST* ps , STDataType x)
{
    if (ps->capacity == ps->top)
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        ps->a = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
        ps->capacity = newcapacity;
    }
    ps->a[ps->top++] = x;
}

bool isValid(char* s) {

    ST s1 = {NULL, 0,0};
    ST* ps = &s1;
    int i = 0;
    while (*(s + i))
    {
        if (*(s + i) == '(' || *(s + i) == '[' || *(s + i) == '{')
        {
            Buynode(ps, (*(s + i)));//入栈
        }
        else
        {
          
            char tmp = *(s + i);

            // )ascii码-1等于(   ]和}ascii码-2等于[和{
            if (ps->top == 0 || (ps->a[ps->top - 1] != tmp - 1 && ps->a[ps->top - 1] != tmp - 2))//判断栈顶是否为0同时判断出栈数据是否匹配
            {
                return false;

            }
            ps->top--;
        }
        i++;
    }
    bool ret = ps->top == 0 ? true : false;///判断栈顶是否为空不为空表示战内还有数据匹配失败
    free(ps->a);//释放
    return ret;
}
